This invention relates to methods and apparatus for designing state machines using tables and object-oriented programming techniques.
Finite state machines are logical systems in which the sequential logic that implements the system has only a fixed number of possible states. When the system is in a given state, it may perform various predefined operations, such as displaying images or calculating results. The logic causes the system to advance from state to state causing the system to sequentially perform various operations. More specifically, when the logic is in a given state, the output and next sequential state are determined by a combinatorial function of the input to the logic and the present state of the logic. State machine approaches are typically utilized when designing and implementing protocols, user interfaces and complex systems involving asynchronous events, and solving other complex problems.
There are many methods for describing the behavior of finite state machines so that the implementing logic can be designed. These methods include abstract state machine notation, state diagrams, state tables, and hardware description languages. FIG. 1 illustrates a very simple state diagram that has four states 100, 102, 104 and 106. When the system is in each of these states, events that are represented by arrows can occur which move the system from one state to another. For example, in the diagram, the initial state 100 is assumed to be xe2x80x9cState 1xe2x80x9d. An event called xe2x80x9cEvent 1xe2x80x9d and represented by arrow 108 causes the logic to advance to a new state 102 called xe2x80x9cState 2.xe2x80x9d The occurrence of another event called xe2x80x9cEvent 2xe2x80x9d and represented by arrow 110 results in the logic moving to another state 104 called xe2x80x9cState 3.xe2x80x9d From xe2x80x9cState 3xe2x80x9d, 104, an xe2x80x9cEvent 3xe2x80x9d or an xe2x80x9cEvent 5xe2x80x9d are possible. The occurrence of xe2x80x9cEvent 5xe2x80x9d, represented by arrow 114, results in the system returning to its original state 100, that is xe2x80x9cState 1.xe2x80x9d Alternatively, the occurrence of xe2x80x9cEvent 3xe2x80x9d, represented by arrow 112, causes the system to advance to a new state 106, called xe2x80x9cState 4.xe2x80x9d While the system is in xe2x80x9cState 4xe2x80x9d, 106, the occurrences of xe2x80x9cEvent 1xe2x80x9d, xe2x80x9cEvent 2xe2x80x9d, xe2x80x9cEvent 3xe2x80x9d, and xe2x80x9cEvent 5xe2x80x9d do not change the system state as indicated by arrow 116. However, another response, such as an error condition may be raised in response to these events. Finally if an event called xe2x80x9cEvent 4xe2x80x9d occurs while the system is in state 106, the system will advance as represented by arrow 118 back to State 1,100.
When state tables are used to describe the logic behavior, the underlying logic is said to be xe2x80x9ctable driven.xe2x80x9d In the communications area, table driven state machines have been used to graphically represent a solution to a communication problem. From the table, the underlying logic can be implemented quickly, often by programming teams. The is particularly true when a state machine is implemented in software. The use of tables also has the added advantage that future changes are relatively easy to implement, and the incidence of possible regressions is reduced or, at least, contained.
An example of a state table is illustrated in FIG. 2 that shows a state table that implements a finite state machine illustrated by the state diagram of FIG. 1. The table has four columns 200, 202, 204 and 206 that represent the current state, an event that occurs, the action taken when the event occurs and the resulting state of the system (which may be the current state), respectively. Each row, such as row 208, represents a particular state and event combination represented by the first two columns 210 and the results which occur represented by the last two columns, 212. As shown in FIG. 2, rows 208 and 214, the system changes from xe2x80x9cState 1xe2x80x9d and xe2x80x9cState 2xe2x80x9d only if event 1 or event 2 occurs as appropriate. As shown by rows 216 and 218, The system can advance from xe2x80x9cState 3xe2x80x9d to two different states if either of events 3 or 5 occur. xe2x80x9cState 4xe2x80x9d advances only if event 4 occurs, but events 1,2,3, and 5 result in an error being reported, and the system remains in the current statexe2x80x94xe2x80x9cState 4.xe2x80x9d
A state table can be directly implemented in software by reproducing the state table in memory and using the current state and an event occurrence as inputs to perform a table lookup. Utilizing this table approach, the behavior of the implementing software becomes more readily apparent. As an example, if the system functionality must be extended at a later date, additional states, events, or functions may be added, and the implications easily understood. This easy expandability allows the system to be readily grown and reduces the exposure to regression. Another advantage of this approach is that the interaction of each of the functions is easily evaluated. Consequently, each of the functions (which normally require the most significant coding effort) can be assigned to a different programmer without requiring extensive coordination.
The problem with implementing the state table as a table lookup in memory is the additional memory required by the table. For large state tables, the amount of memory can be significant. In many cases, the benefits of this approach may outweigh the extra memory required, but in embedded systems, memory may have a more significant expense associated with it, and thus not justify this benefit.
The state table illustrated in FIG. 2 may also be implemented in a more complete form 300 illustrated in FIG. 3. This table is similar to the table illustrated in FIG. 2 except that it has a row representing each possible state and each possible event. For example, State_1 has a row representing each of events Event_1 to Event_5, represented by rows 302-310, respectively. If an event cannot occur in a particular state the Action column 301 is left blank and the NEXT STATE 303 remains the current state. Similarly State 2 has rows 312-320 representing Event_1 to Event_5 and State_3 has rows 322-330 representing Event_1 to Event_5. State_4 has rows 332-340 representing Event_1 to Event_5. A complete matrix like the one illustrated in FIG. 3 forces the implementers to consider the impact of events that are not anticipated, but even more memory is required to implement the table.
Therefore, it is desirable to provide the advantages of a finite state machine implemented with a state table while reducing the amount of memory used in such an implementation as much as possible.
In accordance with the principles of the invention, a finite state machine is implemented by encapsulating the portions of a state table, which are associated with each state in a state object. Each state object is instantiated when the associated state is entered and destroyed when the state is exited. Since memory is only allocated at runtime when an object is instantiated and in existence, the amount of memory required to implement the state table is minimized.
In accordance with one embodiment, the state class from which the state object is instantiated can be subclassed. In accordance with normal object-oriented class design, a subclass inherits the state table of its parent class. However, the subclass allows table rows to be added and table rows present in the parent class to be overwritten in the subclass.
In accordance with another embodiment, state table in each state class includes methods that are called when the class is created and destroyed.